package com.isaiah.queue;

/**
 * @Title: 基于链表的队列实现
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/5/1217:14
 */
public class LinkedListQueue<E> implements Queue<E>{

    /**
     * 定义节点类型
     */
    private class Node{
        /** 数据元素 */
        public E e;
        /**  指向下一个节点的指针 */
        public Node next;

        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /** 头节点 */
    private Node head;

    /** 尾节点 */
    private Node tail;

    /** 元素个数 */
    private int size;

    @Override
    public void enqueue(E e) {
        // 插入时在尾部插入
        if (head == null && tail == null){
            tail = new Node(e);
            head = tail;
        }else{
            // 新创建节点应该在tail.next位置
            tail.next = new Node(e);
            // 维护tail， 新的tail就为刚才创建节点
            tail  = tail.next;
        }
        // 维护size
        size ++;
    }

    @Override
    public E dequque() {
        if(isEmpty()){
            throw new IllegalArgumentException("cannot dequeue from an empty queue");
        }
        // 删除时在头部删除
        Node retNode = head;
        head = head.next;
        // 把要删除的节点断开
        retNode.next = null;
        if (head == null){
            tail = null;
        }
        // 维护size
        size --;
        return retNode.e;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new IllegalArgumentException("cannot dequeue from an empty queue");
        }
        // 直接返回head中的元素e
        return head.e;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");
        Node current = head;
        while (current != null){
            res.append(current + "->");
            current = current.next;
        }
        res.append("NULL tail");
        return res.toString();
    }
}
